public class Solution {
    /*
     * 不同路径问题
     * 状态：F(i,j): 到(i,j)坐标点有多少种路径
     * 状态转移方程：F(i,j) = F(i-1,j) + F(i,j-1)
     * 初始状态：
     *       F(0,j) = 1;
     *       F(i,0) = 1;
     * 返回结果：
     *       F(m-1,n-1)
     *
     * */
    public int uniquePaths(int m, int n) {
        int[][] array = new int[m][n];
        for (int i = 0; i < m; i++) {
            array[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            array[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                array[i][j] = array[i - 1][j] + array[i][j - 1];
            }
        }
        return array[m - 1][n - 1];
    }
    

    /*
     * 状态：F(i,j):到(i,j)坐标点有多少中路径
     * 状态转移方程：if(obstacleGrid[i][j] == 1)    F(i,j) = 0
     *            else F(i,j) = F(i-1,j) + F(i,j-1)
     * 初始状态：
     *         F(0,j) = 1 || 0
     *         F(i,0) = 1 || 0
     * 返回结果：
     *        F(row-1,col-1)
     *
     * */
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] Path = new int[row][col];
        for (int i = 0; i < col; i++) {
            if (obstacleGrid[0][i] == 1) {
                break;
            }
            Path[0][i] = 1;
        }

        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            Path[i][0] = 1;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    Path[i][j] = 0;
                } else {
                    Path[i][j] = Path[i - 1][j] + Path[i][j - 1];
                }
            }
        }

        return Path[row - 1][col - 1];
    }
}